import org.junit.jupiter.api.Test;

public class Main {
    @Test
    public void test() {
        int[] arr = {1, -2, 3, 5, -1};
        int[] arr2 = {1, -2, 3, -8, 5, 1};
        int[] arr3 = {1, -2, 3, -2, 5, 1};

        System.out.println(MaxSubSumOfSequence(arr));
        System.out.println(MaxSubSumOfSequence(arr2));
        System.out.println(MaxSubSumOfSequence(arr3));
    }

    public static int MaxSubSumOfSequence(int[] arr) {
        int max = 0;
        int[] dp = new int[arr.length];
        if (arr[0] > 0) {
            dp[0] = arr[0];
        } else {
            dp[0] = 0;
        }
        for (int i = 1; i < dp.length; i++) {
            if (dp[i - 1] > 0) {
                dp[i] = dp[i - 1] + arr[i];
            } else {
                dp[i] = arr[i];
            }
        }

        for (int value : dp) {
            if(max < value) {
                max = value;
            }
        }
        return max;
    }

}
